class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        while(i > 0 && nums[i] <= nums[i - 1])
        {
            --i; // 从后向前查找第一个非递增的元素
        }
        if(i == 0) // 如果整个序列都是递增的
            reverse(nums.begin(), nums.end());
        else
        {
            int j = n - 1;
            while(j >= 0 && nums[j] <= nums[i - 1])
            {
                --j; // 后向前查找第一个大于 nums[i-1] 的元素
            }
            swap(nums[j], nums[i - 1]); // 交换这两个元素,使排列变大
            // 反转 i 之后的元素（使其变为升序，得到最小排列）
            reverse(nums.begin() + i, nums.end());
        }
    }
};
